#include <iostream>

using namespace std;

// 3. Longest Substring Without Repeating Characters
// https://leetcode.com/problems/longest-substring-without-repeating-characters/description/
//
// 滑动窗口
// 时间复杂度: O(len(s))
// 空间复杂度: O(len(charset))
class Solution
{
public:
    int lengthOfLongestSubstring(string s)
    {

        int freq[256] = {0}; // 记录字符是否出现过

        int l = 0, r = -1; // 滑动窗口为s[l...r]，初始为1个无效窗口
        int res = 0;

        // 在这里, 循环中止的条件可以是r + 1 < s.size(), 想想看为什么?
        while (r + 1 < s.size())
        {
            if (freq[s[r + 1]] == 0)
                freq[s[++r]]++;
            else // r到头，或者已经出现过
                freq[s[l++]]--;

            res = max(res, r - l + 1);
        }
        return res;
    }
};

int main()
{
    cout << Solution().lengthOfLongestSubstring("abcabcbb") << endl; // 3
    cout << Solution().lengthOfLongestSubstring("bbbbb") << endl;    // 1
    cout << Solution().lengthOfLongestSubstring("pwwkew") << endl;   // 3
    cout << Solution().lengthOfLongestSubstring("c") << endl;        // 1
    cout << Solution().lengthOfLongestSubstring("") << endl;         // 0

    return 0;
}